package dp.base;

import java.util.Arrays;

public class Solution_300 {

    int[] memo;

    public int lengthOfLIS(int[] nums) {
        memo = new int[nums.length + 1];
        Arrays.fill(memo, -1);
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, dfs(i, nums));
        }
        return res;
    }

    private int dfs(int i, int[] nums) {
        if (i < 0)
            return 0;
        if (i == 0)
            return 1;
        if (memo[i] != -1) {
            return memo[i];
        }
        int maxLen = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                maxLen = Math.max(maxLen, dfs(j, nums) + 1);
            }
        }
        return memo[i] = maxLen;
    }
}
